class Solution {
    int tmp[50010];
public:
    int reversePairs(vector<int>& nums) {
        int n=nums.size();
        int ret=mergeSort(nums,0,n-1);
        return ret;
    }
    int mergeSort(vector<int>& nums,int left,int right)
    {
        if(left>=right)return 0;
        int ret=0;
        int mid=(left+right)>>1;
        ret+=mergeSort(nums,left,mid);
        ret+=mergeSort(nums,mid+1,right);
        int cur1=left,cur2=mid+1,i=0;
        while(cur1<=mid)
        {
            while(cur2<=right && nums[cur2]>=nums[cur1]/2.0)cur2++;
            if(cur2>right)break;
            ret+=right-cur2+1;
            cur1++;
        }
        cur1=left,cur2=mid+1;
        while(cur1<=mid&&cur2<=right) tmp[i++]=nums[cur1]<=nums[cur2]?nums[cur2++]:nums[cur1++];
        while(cur1<=mid)tmp[i++]=nums[cur1++];
        while(cur2<=right)tmp[i++]=nums[cur2++];
        for(int j=left;j<=right;j++)nums[j]=tmp[j-left];
        return ret;
    }
};
